import java.util.*;


public class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public static int[] LFU (int[][] operators, int k) {
        // write code here
        LinkedHashMap<Integer, int[]> map = new LinkedHashMap<>(k);
        int size = 0;
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0;i<operators.length;i++){
            //opt = 1,set
            if(operators[i][0] == 1){
                // set key:operators[i][1] value:operators[i][2] count:operators - 待定
                int[] tmp = map.get(operators[i][1]);
                //新key
                if(tmp == null){
                    // 满了
                    if(size == k){
                        Integer first = map.keySet().iterator().next();
                        map.remove(first);
                        //新增进去 todo:
                        map = fun(map, operators[i][1], operators[i][2], 1);

                    } else {
                        //todo:
                        map = fun(map, operators[i][1], operators[i][2], 1);
                        size++;
                    }
                } else {
                    //旧key,修改value，count todo:
                    map.remove(operators[i][1]);
                    map = fun(map, operators[i][1], operators[i][2], ++tmp[1]);
                }


            }else {
                // get
                int[] tmp = map.get(operators[i][1]);
                if(tmp == null){
                    res.add(-1);
                } else {
                    //记录value
                    res.add(tmp[0]);
                    //修改次数 todo
                    map.remove(operators[i][1]);
                    map = fun(map, operators[i][1], tmp[0], ++tmp[1]);
                }
            }
        }
        int[] arr = new int[res.size()];
        for(int i = 0;i<res.size();i++){
            arr[i] = res.get(i);
        }
        return arr;

    }
    //插入 - 整个顺序为-先以count排序，count相同时，插入时间顺序排序
    public static LinkedHashMap<Integer, int[]> fun(LinkedHashMap<Integer, int[]> map, int key , int value, int count){
        LinkedHashMap<Integer, int[]> res = new LinkedHashMap<>();
        int size = 0;
        int mapSize = map.size();
        while (size<mapSize){
            int first = map.keySet().iterator().next();
            int[] arr = map.get(first);
            if(arr[1] <= count){
                res.put(first, arr);
                map.remove(first);
            } else {
                int[] tmp = new int[]{value, count};
                res.put(key, tmp);
                break;
            }
            size++;
        }
        while (size<mapSize){
            int first = map.keySet().iterator().next();
            int[] arr = map.get(first);
            res.put(first, arr);
            map.remove(first);
            size++;
        }
        //检查新增的key是否成功新增了，如果没有在把他新增在最后面（例如：这组键值对的count最大，就应该在最后一个）
        if(map.get(key) == null){
            int[] tmp = new int[]{value, count};
            res.put(key, tmp);
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {{1,1,1},{1,2,2},{1,3,3},{1,4,4},{2,4},{2,3},{2,2},{2,1},{1,5,5},{2,4}};
//        int[][] arr ={{1,1,1},{1,2,2},{2,2}};
        LFU(arr, 4);
    }
}